package swardToOffer.struct_3_linkedlist;

/**
 * @Author ChanZany
 * @Date 2021/5/21 15:01
 * @Version 1.0
 * <p>
 * 面试题22：链表中倒数第k个结点
 * 题目：输入一个链表，输出该链表中倒数第k个结点。为了符合大多数人的习惯，
 * 本题从【1】开始计数，即链表的尾结点是倒数第1个结点。例如一个链表有6个结点，
 * 从头结点开始它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个结点是
 * 值为4的结点。
 * n个节点，倒数第k个节点，则其为正数第n-k+1个节点
 * n=6,k=3,->the 4-th node
 * 但是n怎么在只遍历一次的情况下得到呢？
 * 定义两个指针，第一个指针从头指针开始遍历向前走K-1步，第二个指针保持不动
 * 从第k步开始，第二个指针也开始从链表的头指针开始遍历。
 * 由于两个指针的距离保持在k-1,当第一个指针到达链表的尾节点时，则第二个节点正好指向倒数第k个节点
 *
 * 最后，注意鲁棒性！！！
 */
public class KthNodeFromEnd {

    ListNode findKthToTail(ListNode head, int k) throws Exception {
        if (head==null||k <= 0) return null;
        //todo k大于链表长度会报错，但是链表长度未知
        ListNode p1 = head;
        ListNode p2 = head;
        for (int i = 0; i < k - 1; i++) {
            if (p1.next == null) throw new Exception("the k is larger than the length of linkedlist");
            p1 = p1.next;//向前走k-1步
        }
        //p2开始移动
        while (p1.next != null) {
            p1 = p1.next;
            p2 = p2.next;
        }
        //此时的p2指向倒数第k个节点
        return p2;
    }

    public static void main(String[] args) throws Exception {
        KthNodeFromEnd Main = new KthNodeFromEnd();
        int[] nums = {1, 2, 3, 4, 5, 6};
        ListNode head = LinkedListUtils.buildLinkedList(nums);
        System.out.println(Main.findKthToTail(head, 7).val);
    }
}
